package offer_test_20;

import struct.BinaryTreeNode;

//输入两颗二叉树A和B，判断B是不是A的子结构。
public class eighteen_SubstructureInTree {
	public static void main(String[] args) {
		BinaryTreeNode root1 = new BinaryTreeNode();
		BinaryTreeNode node1 = new BinaryTreeNode();
		BinaryTreeNode node2 = new BinaryTreeNode();
		BinaryTreeNode node3 = new BinaryTreeNode();
		BinaryTreeNode node4 = new BinaryTreeNode();
		BinaryTreeNode node5 = new BinaryTreeNode();
		BinaryTreeNode node6 = new BinaryTreeNode();
		root1.leftNode = node1;
		root1.rightNode = node2;
		node1.leftNode = node3;
		node1.rightNode = node4;
		node4.leftNode = node5;
		node4.rightNode = node6;
		root1.value = 8;
		node1.value = 8;
		node2.value = 7;
		node3.value = 9;
		node4.value = 2;
		node5.value = 4;
		node6.value = 7;
		BinaryTreeNode root2 = new BinaryTreeNode();
		BinaryTreeNode a = new BinaryTreeNode();
		BinaryTreeNode b = new BinaryTreeNode();
		root2.leftNode = a;
		root2.rightNode = b;
		root2.value = 8;
		a.value = 9;
		b.value = 2;
		System.out.println(substructTree(root1, root2));
	}

	public static boolean substructTree(BinaryTreeNode compare,
			BinaryTreeNode input) {
		boolean rs = false;
		if (compare != null && input != null) {
			if (compare.value == input.value) {
				rs = judgeequal(compare, input);
			}
			if (!rs) {
				rs = substructTree(compare, input.leftNode);
			}
			if (!rs) {
				rs = substructTree(compare, input.rightNode);
			}

		}
		return rs;
	}

	public static boolean judgeequal(BinaryTreeNode compare,
			BinaryTreeNode input) {
		BinaryTreeNode node = compare;
		if (node == null) {
			return true;
		}
		if (input == null) {
			return false;
		}
		if (node.value != input.value) {
			return false;
		}
		return judgeequal(compare.rightNode, input.rightNode)
				&& judgeequal(compare.leftNode, input.leftNode);

	}
}
